#include<vector>
#include<map>
#include <queue>
#include<string.h>
using namespace std;

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int, vector<int>,less<int>> queue_;
        for (auto it = stones.begin(); it < stones.end(); ++it)
            queue_.push(*it);
        while (queue_.size() > 1) {
            int x = queue_.top();
            queue_.pop();
            int y = queue_.top();
            queue_.pop();
            if (x > y)
                queue_.push(x - y);
        }
        return queue_.empty() ? 0 : queue_.top();
    }
};

//class Solution {
//public:
//    int lastStoneWeight(vector<int>& stones) {
//        auto compare = [](const int& left, const int& right){return left > right; };
//        map<int, int, decltype(compare)> map_(compare);
//        
//        for (auto it = stones.begin(); it < stones.end(); ++it) {
//            map_[*it]++;
//        }
//        while (map_.size()>1) {
//            if (map_.begin()->second % 2 != 0) {
//                int x = map_.begin()->first;
//                map_.erase(map_.begin());
//                int y= map_.begin()->first;
//                map_.begin()->second--;
//                if(map_.begin()->second==0)
//                    map_.erase(map_.begin());
//                map_[x - y]++;
//            }else
//                map_.erase(map_.begin());
//        }
//        return map_.begin()->second % 2 ? map_.begin()->first : 0;
//    }
//};